package cn.edu.jxnu.leetcode.scala

import cn.edu.jxnu.leetcode.TreeNode


/**
 * 子树

572. Subtree of Another Tree (Easy)

Given tree s:
     3
    / \
   4   5
  / \
 1   2

Given tree t:
   4
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:
   4
  / \
 1   2

Return false
 * @author 梦境迷离
 * @time 2018年7月18日
 * @version v1.0
 */
object Leetcode_572_Tree extends App {

    def isSubtree(s: TreeNode, t: TreeNode): Boolean = {
        if (s == null) return false
        isSubtreeWithRoot(s, t) || isSubtreeWithRoot(s.left, t) || isSubtreeWithRoot(s.right, t)
    }

    private def isSubtreeWithRoot(s: TreeNode, t: TreeNode): Boolean = {

        if (s == null && t == null) return true
        if (s == null || t == null) return false
        if (s.value != t.value) return false
        isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right)

    }

}